📜 Generalized Edit Distance for Manuscripts

Help Olivia minimize the cost to transform one manuscript into another

👩‍💻 Olivia's Manuscript Transformation Challenge

🎯 The Mission:

Help Olivia find the minimum cost to transform manuscript1 into manuscript2 using insertion, deletion, or substitution, with costs provided as input.

📋 Requirements:

  • Transform manuscript1 into manuscript2 with minimum cost
  • Handle strings of length 1 to 100
  • Input includes costs for insertion, deletion, substitution
  • Output a single integer: the minimum cost

Input/Output Specifications

  • Input: String m1 (manuscript1), String m2 (manuscript2), Three integers (insertCost, deleteCost, substituteCost)
  • Output: Single integer (minimum cost)

Example 1: m1 = "book", m2 = "back", insertCost=4, deleteCost=3, substituteCost=5

m1:

b
o
o
k

m2:

b
a
c
k

Output: 10 (substitute o→a, o→c)

Example 2: m1 = "history", m2 = "mystery", insertCost=2, deleteCost=3, substituteCost=4

m1:

h
i
s
t
o
r
y

m2:

m
y
s
t
e
r
y

Output: 12 (multiple operations)

⚡ Generalized Edit Distance Explained

How Generalized Edit Distance Works

  1. Dynamic Programming: Use a DP table where dp[i][j] is the minimum cost to transform first i characters of m1 into first j characters of m2
  2. Base Cases: Initialize dp[i][0] = i * deleteCost, dp[0][j] = j * insertCost
  3. Fill Table: For each (i,j), if characters match, copy dp[i-1][j-1]; else, take min of deletion, insertion, substitution with given costs

DP Table Example (m1 = "bo", m2 = "ba", insertCost=4, deleteCost=3, substituteCost=5)

\ 0ba
0048
b304
o635

Cost: 5 (substitute o→a)

Time Complexity

O(n * m)

For filling the DP table (n, m are string lengths)

Space Complexity

O(n * m)

For the DP table

Why Generalized Edit Distance?

  • ✅ Minimizes cost with flexible operation costs
  • ✅ Handles insertion, deletion, substitution
  • ✅ Useful in text comparison, historical analysis
  • ❌ Space-intensive for long strings

🔍 Step-by-Step Edit Distance Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input strings and costs
2. Initialize DP table
3. Fill DP table
4. Display result

Current Manuscripts:

m1:

m2:

DP Table:

🎮 Practice Generalized Edit Distance

Enter strings and costs, then click "Compute Cost"

Test Cases

Example 1: m1 = "book", m2 = "back", costs = [4, 3, 5] → 10

Example 2: m1 = "history", m2 = "mystery", costs = [2, 3, 4] → 12

📊 Algorithm Analysis

Generalized Edit Distance Process

  1. Initialize DP: Set dp[i][0] = i * deleteCost, dp[0][j] = j * insertCost
  2. Fill DP Table: For each (i,j), if characters match, copy dp[i-1][j-1]; else, take min of deletion, insertion, substitution with input costs
  3. Output: Print dp[n][m] (minimum cost)

Time Complexity

O(n * m)

For filling the DP table

Space Complexity

O(n * m)

For the DP table

Key Points

  • Dynamic Programming: Optimizes transformation cost with variable costs
  • Operations: Insertion, Deletion, Substitution with input costs
  • Applications: Text comparison, manuscript analysis, bioinformatics
  • Limitation: Space-intensive for long strings